// Copyright 2024 Tvux
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package _045

// jump
// 上一题是问能不能到达终点，这个题保证可以到达终点，问最小跳跃次数，可以想到贪心算法
func jump(nums []int) int {
	if len(nums) == 1 {
		return 0
	}

	end := 0
	maxPos := 0
	steps := 0

	for i, num := range nums {
		maxPos = max(maxPos, i+num)
		if maxPos >= len(nums)-1 {
			// 已经可以跳到了，直接返回当前跳跃次数+1
			return steps + 1
		}
		if i == end {
			// 遍历到边界之后则更新边界，并且跳跃次数+1
			end = maxPos
			steps++
		}
	}

	return steps
}

// 2 3 1 1 4 值
// 0 1 2 3 4 下标
// maxPos = 0+2 = 2, 2 < 4
// i == end == 0, end = 2, steps++ =1
// maxPos = 1+3 = 4, 4 = 4, return 1+1 = 2
